package DFS_BFS;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @PackageName: DFS_BFS
 * @ClassName: LeetCode934
 * @Author: chen jinxu
 * @Date: 2022/2/24 22:51
 * 在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）
 * 现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。
 * 返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）
 * 输入：A = [[0,1],[1,0]]       0  1
 * 输出：1                       1  0
 * <p>
 * 输入：A = [[0,1,0],[0,0,0],[0,0,1]]     0  1  0
 * 输出：2                                 0  0  0
 *                                         0  0  1
 * <p>
 * 输入：A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
 * 输出：1
 * 1 1 1 1 1
 * 1 0 0 0 1
 * 1 0 1 0 1
 * 1 0 0 0 1
 * 1 1 1 1 1
 */
public class LeetCode934 {
    public static void main(String[] args) {
        int[][] grid = {{0, 1,0}, {0, 0,0},{0,0,1}};
        int result = shortestBridge(grid);
        System.out.println(result);
    }

    // 1. 用来转换方向
    private static final int[][] dirs = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    public static int shortestBridge(int[][] grid) {
        //2. 记录整个图的尺寸
        int row = grid.length;
        int col = grid[0].length;
        // 3. 标记那些文位置已经访问过了
        boolean[][] visited = new boolean[row][col];
        //4. 标记是否找到第一个岛屿了
        boolean findIsland = false;
        // 5. 记录第一个小岛的边界
        Queue<int[]> board = new LinkedList<>();
        // 6. 去标记一个小岛,将原来的1改成2
        for (int i = 0; i < row && !findIsland; i++) {
            for (int j = 0; j < col && !findIsland; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    mark(grid, visited, i, j, 2, board);
                    // mark 执行换后，一个岛屿将被找到，并且全部的1改为了2
                    findIsland = true;   // 退出循环
                }
            }
        }
        // 记录距离
        int ans = 0;
        while (!board.isEmpty()) {
            // 记录当前要遍历的边界数量
            int size = board.size();
            for (int i = 0; i < size; i++) {
                // 取出一个边界
                int[] next = board.poll();
                for (int j = 0; j < 4; j++) {
                    //对这个坐标的上下左右进行检查
                    assert next != null;
                    int rolI = i + dirs[j][0];
                    int colJ = j + dirs[j][1];
                    // 如果这个新坐标合法，而且没有访问过,就对其进行检查
                    if (rolI >= 0 && colJ >= 0 && rolI < rolI && colJ < col && !visited[rolI][colJ] ) {
                        visited[rolI][colJ] = true;
                        // 如果接触到第二个岛屿，那么直接返回距离计数
                        if (grid[rolI][colJ] == 1) {
                            return ans;
                        } else {
                            // 否则，放入边界队列中
                            board.offer(new int[]{rolI,colJ});
                        }
                    }
                }
            }
            ans++;
        }
        return ans;
    }

    /**
     * 对 grid中的一个小岛进行标记
     * @param grid  原图
     * @param visited  某个坐标是否访问过
     * @param i  出发点【i,j】
     * @param j  触发点【i,j】
     * @param color 要标记成的数字
     * @param board  用来保存边界的队列
     */
    private static void mark(int[][] grid, boolean[][] visited, int i, int j, int color, Queue<int[]> board) {
        grid[i][j] = color;
        // 判断当前点是不是岛屿边界（位于图的边缘，或者旁边是0），是的话直接放入到队列中
        if (i == 0 || j == 0 || i == grid.length - 1 || j == grid[0].length - 1
        || grid[i][j - 1] == 0 || grid[i][j + 1] == 0 || grid[i - 1][j] == 0 || grid[i + 1][j] == 0) {
            board.add(new int[]{i, j});
        }
        // 对 【i,j】 上下左右四个方向进行拓展检查
        for (int k = 0; k < 4; k++) {
            int rolI = i + dirs[k][0];
            int rolJ = j + dirs[k][1];
            // 对小岛进行拓展查找
            if (rolI >= 0 && rolI <= grid.length - 1 && rolJ >=0 && rolJ <= grid[0].length - 1 && !visited[rolI][j]
            && grid[rolI][rolJ] == 1) {
                visited[rolI][rolJ] = true;
                mark(grid, visited, rolI, rolJ, color, board);
            }
        }
    }
}
